In order to gain access to applications or other resources via a computer or another user device, users are often required to authenticate themselves by entering authentication information. Such authentication information may include, for example, passcodes that are generated by a security token carried by a user. These passcodes may be, for example, one-time passcodes that are generated using a time-synchronous or event-based algorithm.
Some user authentication systems employ challenge-response techniques. In response to a challenge c, the user provides a response r=f(κ; c), for some cryptographic function f (for example, a hash function) and a secret key κ.
The leakage of cryptographic keys presents a challenge in a number of settings. Computing devices are often vulnerable to side-channel attacks, which extract secret information through channels that are not explicitly designed into the system. Attacks exploiting a wide range of side-channels, e.g., analysis of power, timing and/or faults, are well documented. More recently, side-channels have been studied in virtualized systems that break the isolation abstraction between virtual machines.
In addition to side-channels, exfiltration of key data (i.e., an unauthorized release of such key data) can occur when a device has been compromised by, e.g., a virus or a Trojan horse that removes sensitive device information. For instance, the theft of credentials from mobile devices has become a major industry concern.
A number of techniques have been proposed or suggested for leakage-resilient cryptographic primitives. Leakage-resilient cryptographic primitives are schemes in which, assuming an attacker is able to leak only a limited amount of information from a victim device, the cryptographic primitive remains secure. For scenarios in which leakage occurs through device compromise, most leakage-resilient cryptographic schemes operate within what is known as the bounded storage model of attack. An attacker is presumed to be able to leak data at most l (say, l bits) over the lifetime of a cryptographic private key sk, with corresponding public key pk. A cryptographic primitive secure in this model is regarded as secure if the cryptographic primitive remains unbreakable no matter which l bits of data are leaked.
Leakage-resilient cryptographic schemes in the bounded storage model are typically designed to withstand attacks involving substantial data exfiltration (i.e., large l), and thus employ very large keys sk (a fundamental requirement being that |sk|>l). Practical constraints on the adversary motivate this model, e.g., limited bandwidth available for exfiltration, limited storage available to the attacker and the risk of detection of exfiltration of large amounts of data.
A number of existing leakage-resilient cryptographic schemes have a number of drawbacks. First, the secret key sk consumes considerable storage. While storage is abundant on some devices, it may be costly or prohibitive in many others, e.g., on mobile devices. In addition, key generation is computationally intensive. For example, to compute the secret key sk, full key generation is required for each individual secret key sk[i]. In practice, to generate a key sk of, e.g., 8 Gigabits (Gb), using an underlying exponent size of, e.g., 1024 bits, would require 223 modular exponentiations. For a computationally constrained device, e.g., a mobile device, this computation can be onerous. Finally, online computational requirements are high. For example, on the order of tens of modular exponentiations may be required by the prover and verifier in a practically parameterized setting.
A need therefore exists for improved techniques for generating exfiltration-resilient cryptographic keys that can be used, for example, for authentication and digital signing.